package com.LeetCode.dp;

import org.junit.Test;

/**
 * 高楼扔鸡蛋
 * dp[k][m] 的意义是 有 k 个鸡蛋，可以尝试 m 次，dp[k][m] 的值是 楼的高度 N，
 * 也就是说，给你 k 个鸡蛋，尝试 m 次，最坏情况下可以最多要测试 N 层楼
 *
 * dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1
 * dp[k][m-1] 蛋没碎，尝试次数减一，往高层尝试
 * dp[k-1][m-1] 蛋碎了，蛋的个数减一，尝试次数减一，往底层尝试
 */
public class throwEgg {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K+1][N+1];

        int res = 0;

        while(dp[K][res] < N){
            res++;
            for(int i = K; i > 0; i--){
                dp[i][res] = dp[i][res-1] + dp[i-1][res-1] + 1;
            }
        }
        return res;
    }

    @Test
    public void test(){
        System.out.println(superEggDrop(3,14));
    }
}
